/*
 * @lc app=leetcode.cn id=1202 lang=typescript
 *
 * [1202] 交换字符串中的元素
 */

// @lc code=start

// 并查集
class UnionFind {
  parent: number[];
  size: number[];
  count: number;
  constructor(n: number) {
    this.parent = new Array(n).fill(0).map((_, idx) => idx);
    this.size = new Array(n).fill(1);
    this.count = n;
  }

  find(x: number): number {
    if (x === this.parent[x]) return x;
    this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }

  union(x: number, y: number): void {
    let rx = this.find(x);
    let ry = this.find(y);
    if (rx === ry) return;
    if (this.size[rx] > this.size[ry]) {
      [rx, ry] = [ry, rx];
    }
    this.parent[rx] = ry;
    this.size[ry] += this.size[rx];
    this.count--;
  }
}
// 小顶堆
class MinPQ {
  pq: string[];
  constructor() {
    this.pq = [];
  }
  size(): number {
    return this.pq.length;
  }
  less(i: number, j: number): boolean {
    return this.pq[i].charCodeAt(0) < this.pq[j].charCodeAt(0);
  }
  swap(i: number, j: number): void {
    [this.pq[i], this.pq[j]] = [this.pq[j], this.pq[i]];
  }
  swin(i: number): void {
    let parentIdx = (i - 1) >> 1;
    while (parentIdx >= 0 && this.less(i, parentIdx)) {
      this.swap(i, parentIdx);
      i = parentIdx;
      parentIdx = (i - 1) >> 1;
    }
  }
  sink(i: number): void {
    let childIdx = i * 2 + 1;
    while (childIdx < this.size()) {
      if (childIdx + 1 < this.size() && this.less(childIdx + 1, childIdx)) {
        childIdx++;
      }
      if (this.less(i, childIdx)) return;
      this.swap(i, childIdx);
      i = childIdx;
      childIdx = i * 2 + 1;
    }
  }
  push(x: string) {
    this.pq.push(x);
    this.swin(this.size() - 1);
  }
  pop(): string {
    const min = this.pq[0];
    this.swap(0, this.size() - 1);
    this.pq.pop();
    this.sink(0);
    return min;
  }
}

function smallestStringWithSwaps(s: string, pairs: number[][]): string {
  const size = s.length;
  const unionFind = new UnionFind(size);

  // 将索引对放入并查集
  for (let [x, y] of pairs) {
    unionFind.union(x, y);
  }

  // 将连通的元素放在root为下标的小顶堆中
  const help = new Array(size).fill(0).map(() => new MinPQ());
  for (let i = 0; i < size; i++) {
    const idx = unionFind.find(i);
    help[idx].push(s[i]);
  }

  // 將同一根下的元素从小顶堆中取出
  let result = '';
  for (let i = 0; i < size; i++) {
    const idx = unionFind.find(i);
    result += help[idx].pop();
  }

  return result;
}
// @lc code=end
